/**
 *   @file BinTree.h
 */
#ifndef _BINTREE_H_
#define _BINTREE_H_

#include "../../common/BaseObject.h"
#include "../../util/FuncPtrT.h"

namespace cppflib
{

namespace collections
{

namespace tree
{

class TreeNode;

// callback function to be called when performing a tree walk
typedef util::FuncPtr1T<void, TreeNode*> TreeWalkCallback;

/**
 *  A simple binary search tree
 */
class _DLLAPI BinTree : public BaseObject
{
private:
    TreeNode * m_pRootNode;
    u32_t m_nodeCount;
    TreeWalkCallback * m_treeWalkCB;
    bool m_isReplacedWithPredecessor; 

protected:
    explicit BinTree(bool isReplacedWithPredecessor);

public:
    BinTree(void);
    virtual ~BinTree(void);

    bool IsTreeEmpty(void);
    u32_t GetCount(void);
    TreeNode * GetRootNode(void);
    void SetTreeWalkCallback(const TreeWalkCallback &treeWalkCB);
    
    /**********************************************************
     * The following "pNode" argument (if provided) must be a pointer to the node inside this tree
     **********************************************************/
    void BreathFirstTraverse(TreeNode * pNode = NULL);
    void InorderWalk(void);
    void InorderWalk(TreeNode * pNode);    
    void PreorderWalk(void);    
    void PreorderWalk(TreeNode * pNode); 
    void PostorderWalk(void);   
    void PostorderWalk(TreeNode * pNode);
    TreeNode * GetMin(TreeNode * pNode = NULL);    
    TreeNode * GetMax(TreeNode * pNode = NULL);
    TreeNode * GetSuccessor(TreeNode * pNode);
    TreeNode * GetPredecessor(TreeNode * pNode);
    void RightRotate(TreeNode * pNode);
    void LeftRotate(TreeNode * pNode);

    /*********************************************************
     * The following "node" argument is NOT a node inside this tree
     ********************************************************/
    TreeNode * Search(const TreeNode &node) const;
    virtual bool Insert(TreeNode *pNode);
    virtual bool Delete(const TreeNode &node);
    void FreeTree(void);

protected:
    bool Delete(const TreeNode &node, TreeNode* &pDelParent, bool & isLeftChild);

private:
    void FreeByPostorder(TreeNode * pNode);
};

}  // end of namespace tree

}  // end of namespace collections

}  // end of namespace cppflib


#endif
